A relational database is a collection of logically related data that includes tables (or relations) made up of rows (or tuples) and columns (or attributes). Each row represents an occurrence of an entity defined by a table, with an entity being a person, place, or thing about which the table contains information. To extract data from, or to update, a relational table, queries according to a standard database query language (e.g., Structured Query Language or SQL) are used.
Certain queries call for full-table scans to be performed, which are expensive in terms of resources consumed, especially if the scans are of large tables. A full-table scan refers to reading in sequence all rows of a table. Some database systems, such as those in which a data warehouse is implemented, store very large tables (with millions or even billions of rows). As ad hoc querying of data warehouses is becoming more common, concurrent full-table scans in a database system frequently occur. A large number of full table scans will consume a large portion of the disk I/O capacity in the database system and significantly decrease the amount of disk I/O capacity available to other transactions. To improve performance of concurrent full-table scans, a synchronized scan technique is used, in which two or more transactions that are scanning the same table are grouped together so that disk I/O activities can be shared between them. This reduces the cumulative number of I/O accesses required by the table scans while additionally saving CPU (central processing unit) cycles that would otherwise have been required to process the extra I/O accesses.
When multiple transactions are received in a database system, they are temporarily stored in a scheduling queue. As system resources become available, the transactions in the queue are executed. One such system resource is a buffer pool, which is a cache maintained in system memory for temporarily storing data retrieved from a table. The buffer pool is usually divided into multiple buffer segments, with one buffer pool segment allocated per transaction. As a database system becomes more fully loaded, the buffer pool becomes filled such that no new transactions are admitted for execution. With a conventional buffer management algorithm, after all buffer pool segments (or a large percentage of buffer pool segments) in the buffer pool are committed, no new transactions are allowed to enter the database system for execution. Conventional buffer management algorithms do not take advantage of the synchronized scan technique in admitting new transactions when a buffer pool becomes filled. For example, after all the buffer pool segments are used up, even if some transaction T1 is currently doing a table scan on relation R, a new transaction T2 scanning the same relation R is not allowed to enter the system to join transaction T1.